
\chapter{Análise de código RISCO}
\label{c:analise_codigo}

A atividade de desenvolvimento de software moderno para sistemas embarcados
apresenta requisitos únicos a este nicho, assim como a necessidade de um
ecossistema de ferramentas especializadas como, por exemplo
\cite{es_architecture_guide}: montadores, compiladores, simuladores,
depuradores, \emph{profilers}, analisadores estáticos e otimizadores em tempo
de execução. No capítulo \ref{c:llvm} apresentou-se os argumentos de que a maior
motivação para a criação do projeto LLVM foi a necessidade de um framework de
componentes reutilizáveis que suportassem o desenvolvimento de todos os tipos de
ferramentas necessárias para um sistema de compilação com estas
características \cite{llvm_main_art}, tendo como artefato de unificação a sua
linguagem de representação intermediária, LLVM-IR. No encerramento deste
trabalho, serão apresentadas as análises e ferramentas desenvolvidas para o
estudo e otimização do código RISCO gerado a partir de programas escritos em
linguagens de alto nível. O trabalho descrito no capítulo \ref{c:risco_llvm},
possibilitou o uso destas linguagens para a plataforma RISCO, porém trata-se
apenas do primeiro passo para o suporte completo a um conjunto de ferramentas
com as características mencionadas acima. É preciso um processo de melhoramento
contínuo do módulo RISCO para o LLVM, não apenas a verificação de corretude do
código gerado para os casos de teste descritos na seção
\ref{s:verificacao_codigo}.

As análises realizadas sob o código RISCO consistiram de dois caminhos: estudo
do tamanho do código gerado e análise estática do grafo de fluxo de controle.
Ambos são detalhados neste capítulo. 


\section{Densidade do código}

\citeonline{code_density} trabalha com a definição de \emph{densidade do
código} como sendo uma medida indicativa, em uma dada arquitetura, do número de
instruções necessárias para a implementação de uma determinada funcionalidade:
quanto menor o tamanho do código, maior a sua densidade. Foi considerada a
realização de um outro estudo com relação a eficiência do código gerado quando
comparado a outras alternativas RISC. Entretanto, como o código gerado pelo
módulo RISCO executa sob o simulador \texttt{risco-sim}, a qualidade da
implementação do simulador com relação aos outros simuladores para outros
processadores influenciaria diretamente os resultados, e este não era o objetivo
da comparação. A densidade de código é um atributo particularmente importante no
desenvolvimento de software para sistemas embarcados que apresentam restrições
de memória severas. Nestes casos, quaisquer ganhos na densidade do código são
traduzidos em benefícios reais para a aplicação. O objetivo da análise da
densidade do código RISCO gerado foi entender a eficiência do módulo
\texttt{risco-llvm} com relação a utilização dos padrões de reescrita na
compilação da linguagem intermediária, assim como as características de
eficiência de espaço que são intrínsecas ao conjunto de instruções do
processador.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\textbf{Arquitetura - Otimização} & \textbf{Mínimo} &
\textbf{Máximo} & \textbf{Média} & \textbf{Desvio padrão} \\ \hline
SPARC - O1 & 40 & 1452 & 558.96 & 340.40 \\ \hline
MIPS - O1 & 52 & 1580 & 561.40 & 341.48 \\ \hline
SPARC - O2 & 40 & 1452 & 566.12 & 342.00 \\ \hline
SPARC - O3 & 40 & 1452 & 566.96 & 342.60 \\ \hline
MIPS - O2 & 52 & 1580 & 569.20 & 344.12 \\ \hline
MIPS - O3 & 52 & 1580 & 569.88 & 344.68 \\ \hline
RISCO - O2 & 52 & 2128 & 735.08 & 452.88 \\ \hline
RISCO - O1 & 52 & 2120 & 748.84 & 467.52 \\ \hline
RISCO - O3 & 52 & 2120 & 766.60 & 474.84 \\ \hline
\end{tabular}
\end{center}
\caption[Tamanho dos executáveis gerados para o conjunto de testes no RISCO,
         MIPS e Sparc]
        {Resultados da compilação do conjunto de testes para o RISCO, MIPS e 
         Sparc, utilizando os 3 níveis de otimização (-O1, -O2, -O3): tamanho
         dos segmentos de instruções dos executáveis, em bytes}
\label{tab:code_sizes}
\end{table}

Os testes foram realizados comparando-se o número de instruções emitidas para
todos os programas do conjunto de testes do \texttt{risco-c} (43 programas)
quando compilados para as plataformas RISCO, MIPS \cite{mips32} e SparcV8
\cite{sparcv8}. Note que, para as 3 arquiteturas, restringimos a geração de
código para somente utilizar as instruções de tamanho fixo, todas com 4 bytes.
O número de instruções não é calculado a partir do tamanho do arquivo binário
executável gerado pelo compilador, pois isto iria incluir as informações de
codificação do formato binário de cada plataforma, que não são relevantes. O
número é calculado por uma análise a partir do seu código de montagem, com um
script Python \cite{python_book}. Uma característica dos compiladores modernos
é que o tamanho do código gerado varia com relação ao nível das otimizações
aplicadas sob o código. Desta maneira, para cada plataforma alvo considerada, o
conjunto de testes é compilado 3 vezes, uma vez para cada nível de otimização
disponível no LLVM. Após este passo, continuamos a análise utilizando, para
cada plataforma, a rodada de compilação que gerou a menor média para o número
de instruções emitidas.

A tabela \ref{tab:code_sizes} explicita a influência do nível de otimização no
tamanho do código. A especificação desta opção tem a forma ``-O$n$''. Em
geral, $n$ é uma medida indicadora da agressividade das otimizações utilizadas
pelo compilador \cite{llvm_site}, diretamente relacionada com a
eficiência do código gerado e também com o seu tamanho. A única exceção é a
plataforma RISCO, onde a opção ``-O2'' gerou código de menor tamanho médio com
relação à opção ``-O1''. Para priorizar os menores tamanhos de código, iremos
comparar as alternativas ``RISCO - O2'', ``MIPS - O1'' e ``SPARC - O1''.

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.8]{images/grafico-tamanhos}
  \textsf{\caption{Número médio e máximo de instruções emitidas para o conjunto
                   de programas nas 3 arquiteturas. \label{fig:grafico_sizes}}}
\end{figure}

O gráfico da figura \ref{fig:grafico_sizes} mostra a comparação direta entre as
3 alternativas. É possível notar que tanto para o valor médio quanto para o
máximo, a ordem da maior densidade de código até a menor é: SparcV8, MIPS e
RISCO. Algumas observações pertinentes a esse resultado são:

\begin{itemize}
  \item O fato de que ambos os backends MIPS e Sparc geram código de maior
  densidade que o RISCO não foi uma surpresa. São implementações mais maduras e
  otimizadas \cite{llvm_backend}, enquanto o RISCO ainda implementa somente as
  funcionalidades mais básicas de geração de código.
  
  \item A arquitetura Sparc contêm um conjunto de instruções similar ao MIPS e
  o RISCO. Entretanto, dispõe de um número maior de registradores
  \cite{sparcv8}: ao total são 160 de propósito geral, divididos entre as
  diversas classes como os registradores normais nas janelas de registradores e 
  os registradores específicos para valores em ponto flutuante. Isto pode ter
  influenciado a pequena vantagem observada com relação ao MIPS.
  
  \item O RISCO implementa menos padrões de seleção do que as outras duas
  arquiteturas. Isto gera um menor espaço de soluções na etapa de seleção de
  instruções (subseção \ref{ss:llvm_instruction_selection}).
  
  \item A falta de instruções de multiplicação e divisão faz com que uma
  chamada de subrotina seja feita para cada operação, o que inclui todo o
  processo de salvar e restaurar registradores de acordo com a convenção de
  chamada RISCO32 (subseção \ref{ss:risco32}). Além disso, as operações de salto
  condicionado necessitam de 2 instruções, enquanto nas outras duas arquiteturas
  existem instruções específicas para comparação e salto simultâneos.
\end{itemize}

A principal conclusão desta análise é que, mesmo com as desvantagens apontadas
acima, o seletor de instruções do gerador de código LLVM consegue utilizar o
conjunto reduzido de padrões de seleção do módulo \texttt{risco-llvm} para gerar
código diferente nos 3 níveis de otimização (vide os valores das médias na
tabela \ref{tab:code_sizes}). Isto mostra o potencial de melhora que existe caso
o componente \texttt{RISCOInstrInfo} seja melhorado continuamente, como nos
backends MIPS e Sparc.


\section{Tempo de Execução no Pior Caso}

\abrv[WCET -- Worst Case Execution Time]

\citeonline{wcet_survey} definem a análise do tempo de execução de uma dada
tarefa no pior caso (WCET, do inglês \emph{worst case execution time})
como sendo uma técnica para determinação do maior tempo possível de execução de
um programa em uma plataforma específica. Esta medida pode ser feita, por
exemplo, como o número de ciclos da UCP gastos. Tal análise é de grande
importância para os sistemas de tempo real rígido, onde a corretude do programa
depende da satisfação de todos os seus requisitos temporais (como o cumprimento
dos prazos das tarefas, \emph{deadlines}) \cite{vahid_book}. Uma ferramenta
capaz de estimar o pior tempo de execução de uma tarefa consegue determinar
estaticamente se um dado algoritmo terá sucesso neste ambiente ou não. Um
exemplo de uma ferramenta comercial de sucesso que realiza este tipo de análise
é a coleção ``\emph{aiT WCET Analyzers}'' \cite{wcet_ait}, utilizada no
desenvolvimento de sistemas aviônicos. 

O problema da determinação do WCET para uma dada subrotina de um programa é
indecidível \cite{wcet_survey} (por uma redução trivial ao problema da parada).
Logo, todas as ferramentas existentes para este tipo de análise trabalham com
uma classe restrita de programas que sejam passíveis de análise. As restrições
são específicas a cada ferramenta e dependem da técnica que elas utilizam. Este
tipo de análise é difícil pois um dado trecho de código pode apresentar inúmeros
fluxos de execução distintos, cada um com o seu respectivo tempo de execução.
\citeonline{llvm_wcet} afirma que a ferramenta precisa utilizar heurísticas
próprias para analisar menos caminhos distintos, de modo a terminar a análise em
tempo hábil.

É importante notar que todas as ferramentas existentes não conseguem determinar
o WCET exato mesmo para a classe restrita de programas que é aceita
\cite{wcet_survey}. Elas determinam um \emph{limite superior} para este
valor. Tal limite é útil para as aplicações em sistemas de tempo real,
mencionadas acima. Além disso, o WCET calculado, em geral, só é válido sob a
hipótese de que o programa é o único executando na plataforma hospedeira (host),
em um sistema sem multitarefa.

\subsection{Grafo de Controle de Fluxo}

\abrv[GCF -- Grafo de Controle de Fluxo]

Neste trabalho, desenvolvemos uma ferramenta para a determinação do WCET de
cada função pertencente a uma subclasse de programas em C e C++, quando estes
são executados na plataforma RISCO, utilizando uma análise do grafo de controle
de fluxo correspondente a cada rotina \cite{dragon_book}. Um grafo de controle
de fluxo (GCF) $G(V,E)$, para uma determinada função $F$, é um grafo com as
seguintes propriedades:

\begin{itemize}
  \item Há um nó em $V$ para cada bloco básico $\text{BB}$ em $F$. 
  \item Uma aresta $(\text{b1},\text{b2})$ pertence a $E$ se e somente se
  o bloco $\text{b2}$ é um dos possíveis destinos do bloco $\text{b1}$ em $F$.
\end{itemize}

É possível notar que, como a definição assume que $F$ é dividida em blocos
básicos, o programa deve estar escrito, preferencialmente, em uma linguagem
próxima à linguagem de montagem, utilizando instruções de salto para manipulação
de fluxo. A figura \ref{fig:gcf_exemplo} mostra o GCF equivalente a um trecho de
uma sub-rotina na linguagem de montagem do RISCO. É possível notar também que o
grafo é extraído diretamente da definição dos rótulos e das instruções
terminadoras dos blocos básicos. Outra característica relevante é que os ciclos
deste grafo indicam os \emph{laços} de um programa \cite{dragon_book}.

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.8]{images/gcf-exemplo}
  \textsf{\caption{Exemplo de grafo de controle de fluxo
                   \label{fig:gcf_exemplo}}}
\end{figure}

Para definir a classe de programas que é aceita pela ferramenta, precisamos
introduzir os seguintes conceitos \cite{gcf_dom_tree}:

\simb[$u \gg v$ -- $u$ domina $v$ (em um grafo de controle de fluxo)]

\begin{description}
  \item[Nó inicial] Nó que representa o bloco básico de entrada da função. Pode
  ser introduzido artificialmente caso não exista de início. É o único com grau
  0 de entrada.

  \item[Relação de dominância] Em um grafo $G$, um nó $u$ domina um nó $v$
  ($u \gg v$) se e somente se todos os caminhos do nó inicial até $v$ passam por
  $u$.
  
  \item[Aresta de retorno] Uma aresta $(u,v) \in G$ tal que $v \gg u$.
  
  \item[Árvore de dominância] É a árvore $\text{Dom}(G)$ onde: o conjunto de
  vértices é o mesmo de G; a raiz é o nó inicial de $G$; dado um nó $u \in
  \text{Dom}(G)$ e um nó $v$ descendente de $u$, têm-se que $u \gg v$. A árvore
  de dominância correspondente ao GCF da figura \ref{fig:gcf_exemplo} está na
  figura \ref{fig:gcf_domtree}.
\end{description}

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.8]{images/gcf-exemplo-domtree}
  \textsf{\caption{Exemplo de árvore de dominância
                   \label{fig:gcf_domtree}}}
\end{figure}

São conceitos essenciais para as análises de fluxo de dados nos compiladores
modernos \cite{llvm_site}. Para este trabalho, são conceitos necessários para a
definição de \emph{laço natural}. Um laço natural apresenta as seguintes
propriedades\footnote{A definição apresentada por \citeonline{natural_loop} é
mais abrangente, incluindo laços com mais de uma aresta de retorno. Na
ferramenta, estes laços não são suportados.} \cite{natural_loop}: o seu nó
inicial domina todos os nós do laço (1); tem uma única aresta de retorno nos
seus nós internos, cujo destino é o nó inicial do laço e cujo nó fonte é
denominado de nó final do laço (2); contêm o menor conjunto de nós que inclui o
inicial e o final e não tem predecessores fora do conjunto (3). Segundo a
definição, o laço apresentado no GCF da figura \ref{fig:gcf_exemplo} é um laço
natural.

A árvore de dominância de um GCF, neste contexto, serve para identificar
facilmente as arestas de retorno e, consequentemente, os laços naturais do
código. E o conceito de laço natural foi introduzido para restringir o conjunto
de programas que a ferramenta de cálculo do WCET para programas RISCO admite:
só são aceitos aqueles em que todos os laços são naturais. Na prática, isto
restringe os programas em C e C++ que utilizam formas menos tradicionais de
laços, tais como aqueles que fazem uso do comando \texttt{continue}.

\subsection{RISCO-CFG}

A ferramenta denominada \texttt{risco-cfg} faz uso de funcionalidades da
plataforma LLVM para implementar a análise de WCET para programas executados na
plataforma RISCO. Uma outra implementação semelhante (que também utiliza o LLVM)
é descrita em \cite{llvm_wcet}. A ferramenta descrita aqui difere tanto na
técnica utilizada para cálculo do WCET, assim como no fato de ser específica ao
processador RISCO. O objetivo deste componente é determinar, para um dado módulo
LLVM-IR, uma fórmula que descreva o número máximo de ciclos gastos na execução
de uma função quando fornecida a sua entrada de pior caso. A fórmula não é
fechada, e pode conter incógnitas correspondentes aos valores de entrada da
função.

O cálculo do WCET em si é realizado combinando informações de dois grafos de
controle de fluxo: um para o código em representação intermediária e outro para
o código em linguagem de montagem, como será detalhado adiante usando como
exemplo o programa \ref{alg:exemplo_wcet}. 

\begin{algorithm}[htb]
  \centering
\begin{verbatim}

    void test_tepc(int a, int b, int c) {
     for (int i = 5; i < a+10; ++i)
       cout << '*';

     for (int i = 0; i < b-10; ++i)
       cout << '*';

     for (int i = c; i < a+b; ++i)
       cout << '*';
    }
\end{verbatim}
\textsf{\caption{Rotina exemplo para cálculo do WCET \label{alg:exemplo_wcet}}}
\end{algorithm}

A primeira etapa da execução do \texttt{risco-cfg} cria o GFC baseado no código
em linguagem de montagem da função \texttt{test\_tepc}, denominado
\emph{GFC-AS}. Cada bloco básico do GFC-AS contêm instruções nativas do RISCO.
Internamente, a ferramenta calcula para cada bloco básico o número de
instruções de cada tipo (aritmético/lógico, acesso a memória, salto ou chamada
de subrotina) e armazena esta tabela na memória. O segundo passo é a geração do
\emph{GFC-IR}, o grafo de controle de fluxo equivalente ao código em LLVM-IR. O
GFC-IR equivalente ao código do exemplo \ref{alg:exemplo_wcet} está na figura
\ref{fig:gfc_ir_wcet}. Com este grafo, é possível associar as informações dos
tipos de instruções obtidas no grafo GFC-AS com os blocos básicos do GFC-IR.
Além disso, o \texttt{risco-cfg} utiliza a análise \texttt{LoopPass}
\cite{llvm_site} do LLVM para identificar os laços naturais do programa e o
número de iterações de cada um\footnote{O número de iterações nem sempre pode
ser calculado facilmente e, quando retornado, pode depender dos valores dos
parâmetros da função}. 

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.3]{images/gcf-ir-tepc}
  \textsf{\caption{GFC-IR para o exemplo \ref{alg:exemplo_wcet}
                   \label{fig:gfc_ir_wcet}}}
\end{figure}

A terceira etapa utiliza as informações obtidas com os dois grafos anteriores
para formar um conjunto de possíveis expressões para o WCET da função. O
procedimento utilizado é: para todo possível caminho de execução da função,
calcular o tempo estimado (TE) deste caso e adicionar no conjunto.

\begin{algorithm}[htb]
  \centering
\begin{verbatim}

te_memo = { };     // mapeamento nó -> fórmula
te_set = { };      // conjunto das fórmulas já encontradas

função calcula_tecp(node, acumulador_te):
  te_memo[node] = acumulador_te
  acumulador_te += custo(node)
  
  se node contêm a instrução "ret":
    te_set.insert(acumulador_te)
    te_memo.remove(node)
    retorne
  
  se node for o nó final de um laço natural:
    inicio_loop = nó inicial do laço
    custo_interno_loop = acumulador_te - te_memo[inicio_loop]
    custo_loop = custo_interno_loop * #iterações do laço
    
    acumulador_te = te_memo[inicio_loop] + custo_loop
    
    para todo vizinho N de node que não seja inicio_loop:
      calcula_tecp(N, acumulador_te)
  senão:
    para todo vizinho N de node:
      calcula_tecp(N, acumulador_te)

  te_memo.remove(node)
  retorne
\end{verbatim}
\textsf{\caption{Algoritmo para cálculo do WCET \label{alg:wcet}}}
\end{algorithm}

O algoritmo utilizado é descrito no exemplo \ref{alg:wcet}. A idéia do algoritmo
é percorrer todos os caminhos do GFC-IR utilizando uma busca em profundidade e
mantendo o tempo de execução atual do percurso (na variável
\texttt{acumulador\_te}) e dos predecessores do nó atual (na tabela
\texttt{te\_memo}). Ao encontrar o nó final de um laço, o algoritmo determina o
custo total de execução do laço e não retorna para o seu nó de início,
continuando com o percurso a partir de outros sucessores do nó final.

Este algoritmo apresenta complexidade exponencial no número de blocos básicos,
pois trata-se de uma busca exaustiva. Para o cálculo das fórmulas, foi utilizada
uma biblioteca de matemática simbólica denominada \emph{SymPy} \cite{sympy}. O
uso desta biblioteca automatizou a tarefa de manipulação dos polinômios com
incógnitas no cálculo do TECP propriamente dito. Aplicando a ferramenta ao
exemplo \ref{alg:exemplo_wcet}, pode ser visto que, para os diferentes valores
de \texttt{a}, \texttt{b} e \texttt{c}, existem diferentes fluxos de execução
que passam por mais ou menos blocos básicos. No pior caso, a execução passa
pelos três laços e a fórmula de WCET obtida foi:

\begin{quote}
\begin{verbatim}
    4*et_jmp + 10*et_mem + 29*et_arl +
    (5 + a) * (et_call + print_char() + 2*et_jmp + 5*et_arl) +
    (a + b - c) * (et_call + et_jmp + print_char() + 4*et_arl) -
    (10 - b) * (et_call + print_char() + 2*et_jmp + 5*et_arl)
\end{verbatim}
\end{quote}

Onde:

\begin{itemize}
  \item \emph{et\_arl, et\_mem, et\_jmp e et\_call}: São os custos de cada tipo
  de instrução da plataforma RISCO.
  
  \item \emph{print\_char()}: É o custo de uma execução da rotina
  \texttt{print\_char}.
  
  \item \emph{a, b e c}: São os valores dos parâmetros da rotina.
\end{itemize}

Este é um exemplo construído cuidadosamente para mostrar o funcionamento ideal
da ferramenta. Na prática, para a maioria dos programas do conjunto de testes, a
análise \texttt{LoopPass} da plataforma LLVM não consegue determinar o número de
iterações de todos os seus laços, ou então o programa contêm laços que não sejam
naturais.
